package linkedList;

/**
 * 删除排序链表中的重复元素 -83
 *
 * @author yyz
 * @create 2023-11-21 16:31
 */
public class 删除排序链表中的重复元素 {
    /**
     * 删除排序链表中重复的节点，保留不重复的节点
     * @param head 链表的头节点
     * @return 删除重复节点后的链表头节点
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 如果链表为空或者只有一个节点，直接返回链表头
        if (head == null || head.next == null) {
            return head;
        }
        // 创建指针p1指向头节点
        ListNode p1 = head;
        ListNode p2; // 定义指针p2
        // 遍历整个链表
        while ((p2 = p1.next) != null) {
            // 如果当前节点和下一个节点值相等，说明重复出现了
            if (p1.val == p2.val) {
                // 删除重复节点，将p1.next指向p2.next
                p1.next = p2.next;
            } else {
                // 如果当前节点和下一个节点值不相等，没有重复，将p1指向下一个节点
                p1 = p1.next;
            }
        }
        // 返回处理好重复节点后的链表头节点
        return head;
    }

    /**
     * 删除排序链表中重复的节点，保留不重复的节点(递归实现)
     * @param p 链表的头节点
     * @return 删除重复节点后的链表头节点
     */
    public ListNode deleteDuplicates2(ListNode p) {
        if (p == null || p.next == null) {
            // 如果链表为空或者只有一个节点，则直接返回该节点，无需进行删除操作
            return p;
        }

        if (p.val == p.next.val) {
            // 如果当前节点p的值与下一个节点p.next的值相等，则说明存在重复元素
            // 直接递归调用deleteDuplicates2(p.next)，跳过重复元素并返回后面的节点
            return deleteDuplicates2(p.next);
        } else {
            // 如果当前节点p的值与下一个节点p.next的值不相等，则说明不存在重复元素
            p.next = deleteDuplicates2(p.next);
            // 将p的下一个节点指向递归调用deleteDuplicates2(p.next)后的结果
            // 再返回p本身。这样能够确保链表中所有重复元素都被删除，并保持链表的顺序。
            return p;
        }
    }


    public static void main(String[] args) {
        ListNode list = ListNode.of(1,1,2,3,3);
//        ListNode list = ListNode.of();
        System.out.println(new 删除排序链表中的重复元素().deleteDuplicates2(list));
    }
}
